package com.chy.算法;

import org.junit.Test;

import java.util.*;

public class sort {

    @Test
    public void test04(){
//        Stack stack1 = new Stack();
//        Stack stack2 = new Stack();
//        stack1.push("1");
//        stack1.push("2");
//        Object pop = stack1.pop();
//        System.out.println(pop);
//        int[] a = {1,5,3,5,9,2};
//        int[] ints = mergeSort(a);
//        for (int i=0;i<ints.length;i++){
//            System.out.print(ints[i]);
//        }
        double[] b = {1,3,9,1,2,5,4};
//        quickSort(b,0,b.length-1);
        bucketSort(b);
//        int[] ints = mergeSort(b);
//        int a = 1;
    }

    //二分查找
    public int binarySearch(int[] arr,int value){
        int low = 0;
        int hight = arr.length - 1;
        int mid = 0;
        while (low <= hight){
            mid = (low + hight) / 2;
            if (arr[mid] == value){
                return value;
            }else if (arr[mid] < value){
                low = mid + 1;
            }else {
                hight = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 桶排序
     * @param array
     */
    public void bucketSort(double[] array){
        //1.得到数列的最大值和最小值，并算出差值d
        double max = array[0];
        double min = array[0];
        for(int i=1; i<array.length; i++) {
            if(array[i] > max) {
                max = array[i];
            }
            if(array[i] < min) {
                min = array[i];
            }
        }
        double d = max - min;
        //2.初始化桶,我们这里创建的桶数量等于原始数列的元素数量，除了最后一个桶只包含数列最大值，前面各个桶的区间按照比例确定。
        // 区间跨度 = （最大值-最小值）/ （桶的数量 - 1）
        int bucketNum = array.length;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketList.add(new LinkedList<Double>());
        }
        //3.遍历原始数组，将每个元素放入桶中
        for(int i = 0; i < array.length; i++){
            //定位元素属于第几个桶，是按照比例来定位：
            int num = (int)((array[i] - min)  * (bucketNum-1) / d);
            bucketList.get(num).add(array[i]);
        }
        //4.对每个通内部进行排序
        for(int i = 0; i < bucketList.size(); i++){
            //JDK底层采用了归并排序或归并的优化版本
            Collections.sort(bucketList.get(i));
        }
        //5.输出全部元素
        double[] sortedArray = new double[array.length];
        int index = 0;
        for(LinkedList<Double> list : bucketList){
            for(double element : list){
                sortedArray[index] = element;
                index++;
            }
        }
        System.out.println(Arrays.toString(sortedArray));
    }

    //计数排序1
    public void countSort(int[] array) {
        //1.得到数列的最大值
        int max = array[0];
        for(int i=1; i<array.length; i++){
            if(array[i] > max){
                max = array[i];
            }
        }
        //2.根据数列最大值确定统计数组的长度
        int[] countArray = new int[max+1];
        //3.遍历数列，填充统计数组
        for(int i=0; i<array.length; i++){
            countArray[array[i]]++;
        }
        //4.遍历统计数组，输出结果
        int index = 0;
        int[] sortedArray = new int[array.length];
        for(int i=0; i<countArray.length; i++){
            for(int j=0; j<countArray[i]; j++){
                sortedArray[index++] = i;
            }
        }
        System.out.println(Arrays.toString(sortedArray));
    }

    //计数排序2
    public void countSort2(int[] array) {
        //1.得到数列的最大值和最小值，并算出差值d
        int max = array[0];
        int min = array[0];
        for(int i=1; i<array.length; i++) {
            if(array[i] > max) {
                max = array[i];
            }
            if(array[i] < min) {
                min = array[i];
            }
        }
        int d = max - min;
        //2.创建统计数组并统计对应元素个数
        int[] countArray = new int[d+1];
        for(int i=0; i<array.length; i++) {
            countArray[array[i]-min]++;
        }
        //4.遍历统计数组，输出结果
        int index = 0;
        int[] sortedArray = new int[array.length];
        for(int i=0; i<d+1; i++){
            for(int j=0; j<countArray[i]; j++){
                sortedArray[index++] = i + min;
            }
        }
        System.out.println(Arrays.toString(sortedArray));
    }

    //快速排序  【不稳定】
    public void quickSort(int[] arr, int begin, int end){
        //校验：递归终止条件
        if (arr.length <= 1 || begin >= end){
            return;
        }
        //进行分区得到分区下标
        int pivotIndex = partition2(arr,begin,end);
        //递归，左侧快排
        quickSort(arr,begin,pivotIndex-1);
        //递归，右侧快排
        quickSort(arr,pivotIndex+1,end);
        System.out.println("kuaipai"+Arrays.toString(arr));
    }
    //快速排序，返回某一个序列的基准点并排序
    private int partition2(int[] arr, int low, int high){
        //默认使用序列最后一个元素作为基准点
        int pivot = arr[low];
        while (low < high){
            while (low < high && arr[high] >= pivot){
                --high;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot){
                ++low;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }

    //快速排序，交换方法
    private void swap(int[] arr, int i, int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    /**
     *  归并排序算法
     *  归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，
     *  然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了
     */
    public int[] mergeSort(int[] array){
        if (array.length < 2){
            return array;
        }
        //将数组从中间拆分成左右两部分
        /*
            [1,2,3]
         */
        int mid = array.length/2;
        int[] left = Arrays.copyOfRange(array,0,mid);   //[1]               [2]
        int[] right = Arrays.copyOfRange(array,mid,array.length);   //[2,3]       [3]
        int[] sortLeft = mergeSort(left);   //[1]                                   [2]
        int[] sortRight = mergeSort(right); //[2,3]                                 [3]
        //return merge(mergeSort(left),mergeSort(right));
        return merge(sortLeft,sortRight);
    }
    //归并排序,合并两个有序数组并返回新的数组
    private int[] merge(int[] left, int[] right) {
        //创建一个新数组,长度为两个有序数组的长度之和
        int[] array = new int[left.length+right.length];

        //定义两个指针,分别代表两个数组的下标
        int lindex = 0;
        int rindex = 0;
        for (int i=0;i<array.length;i++){
            //左边的指针移动到末尾，说明左边的元素全都塞进去了，此时添加右边的元素即可
            if (lindex >= left.length){
                array[i] = right[rindex++];
            } else if (rindex >= right.length){
                //右边的指针移动到末尾，说明右边的元素全都塞进去了，此时添加左边的元素即可
                array[i] = left[lindex++];
            } else if (left[lindex] < right[rindex]){
                array[i] = left[lindex++];
            } else {
                array[i] = right[rindex++];
            }
        }
        return array;
    }

    /**
     *  希尔排序,  【不稳定】
     *     希尔排序是将一个原序列分成几个子序列，对于每个子序列来所都进行一次插入排序，而依据不同的子序列划分大小，
     *     最后子序列为1时，进行的那一次插入排序跟原来的插入排序就是一模一样的了，只不过现在的队列比原来的要有序的多。
     */
    public void shellSort(int[] array){
        //1.根据数组a的长度，确定增长量h的初始值；
        int h = 1;
        while(h<array.length/2){
            h=2*h+1;
        }
        while(h>=1){
            //排序
            //2.1.找到待插入的元素
            for (int i=h;i<array.length;i++){
                //2.2把待插入的元素插入到有序数列中
                for (int j=i;j>=h;j-=h){
                    //待插入的元素是a[j],比较a[j]和a[j-h]
                    if (array[j-h] > array[j]){
                        int temp;
                        temp = array[j-h];
                        array[j-h] = array[j];
                        array[j] = temp;
                    }else{
                        //待插入元素已经找到了合适的位置，结束循环；
                        break;
                    }
                }
            }
            //减小h的值
            h= h/2;
        }
        System.out.println(Arrays.toString(array));
    }

    /**         插入排序3
     * *  我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，
     *    就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适
     *    的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为，算法结束。
     * @param array
     */
    public void insertionSort3(int[] array) {
        int i, j;         //5 3 4 6  //5 5 4 6  //3 5 4 6  //3 5 5 6  //3 4 5 6
        for(i = 1; i < array.length; i++) {
            for(j = i; j > 0; j--) {
                if(array[j-1] > array[j]) {
                    int temp;
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                }else {
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }

    //选择排序，每次循环都找到最小值，放到当前位置，指针后移   [不稳定]
    public void selectSort(int[] array){
        int length = array.length;
        if (length <= 1){
            return ;
        }
        for (int i=0;i<length;i++){

            int minIndex = i;
            //从未排序的区间中找最小值
            for (int j=i;j<length;j++){
                if (array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i){
                int temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
        }
        System.out.println(Arrays.toString(array));
    }

    @Test
    public void dasda(){
//        insertionSort3(new int[]{3,5,2,1,9,4});
        shellSort(new int[]{3,5,2,1,9,4});
//        bubbleSort(new int[]{3,5,2,1,9,4});
    }
    //冒泡排序
    public void bubbleSort(int[] array){
        int length = array.length;
        if (length <= 1){
            return ;
        }
        for (int i=0;i<length-1;i++){   //循环的次数
            boolean flag = true;
            for (int j=0;j<length-i-1;j++){ //每次循环完把最大的放到最后
                int temp = 0;
                if (array[j] > array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = false;
                }
            }
            if (flag == true){
                break;
            }
        }
//        for (int i=0;i<length;i++){
//            System.out.print(array[i]);
//        }
        System.out.println(Arrays.toString(array));
    }

    //快速排序，返回某一个序列的基准点并排序
    private int partition(int[] arr, int begin, int end){
        //默认使用序列最后一个元素作为基准点
        int pivot = arr[end];
        //定义分区后的pivot元素下标，先定到最左边（左边小-中间是pivot-右边大）
        int pivotIndex = begin;
        for (int i=begin;i<end;i++){
            //判断如果该区间内元素小于pivot，则将元素从区间头开始一直向后填充，小的放在左边
            if (arr[i] < pivot){
                if (i > pivotIndex){    //i每次都会+1，但是pivotIndex只有在元素比pivot小的时候才+1
                    //交换
                    /*
                        i=0 pivotIndex=0    [1,3,5,1,4,2]   i=0 pivotIndex=1
                        i=1 pivotIndex=1    [1,3,5,1,4,2]   i=1 pivotIndex=1
                        i=2 pivotIndex=1    [1,3,5,1,4,2]   i=2 pivotIndex=1
                        i=3 pivotIndex=1    [1,1,5,3,4,2]   i=3 pivotIndex=2
                        i=4 pivotIndex=2    [1,1,5,3,4,2]   i=4 pivotIndex=2
                     */
                    swap(arr,i,pivotIndex);
                }
                pivotIndex++;   //左边（小的区）增大1
            }
        }
        // pivotIndex=2 end=5    [1,1,5,3,4,2] -> [1,1,2,3,4,5]
        swap(arr,pivotIndex,end);
        return pivotIndex;
    }

    /**插入排序
     * 我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，
     * 就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适
     * 的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为，算法结束。
     */
    public void insertionSort(int[] arr){
        int length = arr.length;
        if (length <= 1){
            return ;
        }
        for (int i = 1; i < length; i++) {
            //默认第一个区间已经排序完成，所以i从1开始，之后的区间是未排序的
            int temp = arr[i];
            //在有序区间从后往前查找，如果当前元素比较小，就一直往前移  [1,3,4,  2]
            int preIndex = i - 1;
            while (preIndex >= 0 && arr[preIndex] > temp){
                //说明当前元素比较小，再往前移
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
    //插入排序2
    public void insertionSort2(int[] array) {
        int i, j, temp;         //5 3 4 6  //5 5 4 6  //3 5 4 6  //3 5 5 6  //3 4 5 6
        for(i = 1; i < array.length; i++) {
            temp = array[i];
            for(j = i-1; j >= 0; j--) {
                if(temp > array[j]) {
                    break;
                }else {
                    array[j+1] = array[j];
                }
            }
            array[j+1] = temp;
        }
        System.out.println(Arrays.toString(array));
    }

    //计数排序
    public void countingSort(int[] array) {
        //求出待排序数组的最大值,最小值,找出取值区间
        int max = array[0];
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        //定义一个额外的数组 C
        int bucketSize = max - min + 1;
        int[] bucket = new int[bucketSize];
        //统计对应元素的个数,数组的下标不是单纯的值
        for (int i = 0; i < array.length; i++) {
            int bucketIndex = array[i] - min;
            bucket[bucketIndex] += 1;
        }
        //创建临时数组 R 存储最终有序的数据列表
        int[] temp = new int[array.length];
        //扫描待排序数组
        int j = 0;
        for (int i = 0; i < bucket.length; i++) {
            int value = i + min;  //bucket的下标对应的值，bucket[i]代表有几个
            while (bucket[i] > 0) {
                temp[j++] = value;
                bucket[i]--;
            }

        }
        //将临时数据列表依次放入原始数组
        for (int i = 0; i < temp.length; i++) {
            array[i] = temp[i];
        }
        System.out.println(Arrays.toString(array));
    }
    /**
     * 桶排序
     * @param array 待排序集合
     * @param bucketSize 桶中元素类型的个数即每个桶所能放置多少个不同数值
    （例如当 BucketSize==5 时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不
    限，即可以存放 100 个 3）
     * @return 排好序后的集合
     */
    public static List<Integer> bucketSort(List<Integer> array, int bucketSize){
        if(array == null || array.size() < 2 || bucketSize < 1){
            return array;
        }
        //找出集合中元素的最大值,最小值
        int max = array.get(0);
        int min = array.get(0);
        for(int i=0 ;i < array.size();i++){
            if(array.get(i) > max){
                max = array.get(i);
            }
            if(array.get(i) < min){
                min = array.get(i);
            }
        }
        //计算桶的个数 最大值-最小值代表了集合中元素取值范围区间
        int bucketCount = (max - min )/bucketSize +1;
        //按序创建桶,创建一个 List,List 带下标是有序的,List 中的每一个元素是一个桶,也用 List 表示
        List<List<Integer>> bucketList = new ArrayList<>();
        for(int i=0;i< bucketCount;i++){
            bucketList.add(new ArrayList<Integer>());
        }
        //将待排序的集合依次添加到对应的桶中
        for(int j=0; j< array.size();j++){
            int bucketIndex = (array.get(j)-min)/bucketSize;
            bucketList.get(bucketIndex).add(array.get(j));
        }
        //对每一个桶中的数据进行排序(可以使用别的排序方式),然后再将桶中的数据依次取出存放到一个最终的集合中
        //创建最终的集合
        List<Integer> resultList = new ArrayList<>();
        for(int j=0;j < bucketList.size(); j++){

            List<Integer> everyBucket = bucketList.get(j);
            //如果桶内有元素
            if(everyBucket.size()>0){

                //递归的使用桶排序为每一个桶进行排序
                //当某次桶排序待排序集合都分配到一个桶中时,缩小桶的范围以获得更多的桶
                if(bucketCount ==1){
                    bucketSize--;
                }
                List<Integer> temp = bucketSort(everyBucket, bucketSize);
                for(int i=0;i<temp.size();i++){
                    resultList.add(temp.get(i));
                }
            }
        }
        return resultList;
    }
    /**
     * 测试桶排序
     */
    @Test
    public void testBucketSort(){
        List<Integer> list = new ArrayList<>();
        list.add(5);
        list.add(2);
        list.add(2);
        list.add(6);
        list.add(9);
        list.add(0);
        list.add(3);
        list.add(4);
        System.out.println(list);
        List<Integer> bucketSort = bucketSort(list, 2);
        System.out.println(bucketSort);
        countingSort(new int[]{5,2,2,6,9,0,3,-1,-2});
    }
}
